#include "junix.h"
using namespace std;

void jmerge1(int v[], int p, int q, int r) {
	vector<int> v1(v+p, v+q),v2(v+q,v+r);
	vector<int>::iterator p2 = v1.begin(), q2=v2.begin();
	int* k=v+p;
	while (p2!=v1.end() && q2!=v2.end()) {
		if (*p2<*q2)
			*k++=*p2++;
		else 
			*k++=*q2++;
	}

	if (p2!=v1.end()) 
		copy(p2,v1.end(),v+k);
	else 
		copy(q2,v2.end(),v+k);
}

void jmerge2(int v[], int p, int q, int r) {
	vector<int> v2;
	v2.reserve(r-p);

	int q2=q, p2 =p;
	while (p<q && q2<r) {
		if (v[p]<v[q2])
			v2.push_back(v[p++]);
		else 
			v2.push_back(v[q2++]);
	}

	if (p<q)
		copy(v+p,v+q,back_inserter(v2));
	else
		copy(v+q2,v+r,back_inserter(v2));

	copy(v2.begin(),v2.end(),v+p2);
}

void jmerge3(int v[],int p,int q,int r) {
	int v2[r-p];
	int p2=p,q2=q,k=0;
	while (p2<q && q2<r) {
		if (v[p2]<v[q2])
			v2[k++]=v[p2++];
		else
			v2[k++]=v[q2++];
	}

	if (p2<q)
		copy(v+p2,v+q,v2+k);
	else 
		copy(v+q2,v+r,v2+k);

	copy(v2,v2+r-p,v);
}

int main(int argc, char **argv)
{
	int v[]={5,6,7,8,9,0,1,2,3,4};
	jmerge3(v,0,5,10);
	copy(v,v+10,ostream_iterator<int>(cout," "));
	cout<<"\n";
}
